//
// Created by Administrator on 2021/6/7.
//

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        // 照顾到负数,所有的坐标+1000
        int n = (int) nums.size();
        vector<int> f(2001, 0);
        ++f[1000 + nums[0]];
        ++f[1000 - nums[0]];
        for (int i = 1; i < n; ++i) {
            vector<int> g(2001, 0);
            // 每位数的影响  包括正负
            for (int j = -1000; j < 1001; ++j) {
                if (f[j + 1000] > 0) {
                    g[j + 1000 + nums[i]] += f[j + 1000];
                    g[j + 1000 - nums[i]] += f[j + 1000];
                }
            }
            f = g;
        }
        return f[target + 1000];

    }
};

class Solution2 {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        for (int &num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int neg = diff / 2; // 需要被设为负数的总和
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int &num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
};

int main() {
    Solution2 sol;
    vector<int> nums{1, 1, 1, 1, 1};
    cout << sol.findTargetSumWays(nums, 3) << endl;
    return 0;
}